Regiony
Limit pamięci: 128 MB
Agencja Rozwoju Regionalnego Narodów Zjednoczonych (UNRDA) ma dobrze zdefiniowaną
strukturę organizacyjną.
Zatrudnia łącznie osób, z których każda pochodzi z jednego z regionów
geograficznych świata.
Pracownicy są ponumerowani od do w porządku ważności, przy czym pracownik
numer , Dyrektor, jest najważniejszą osobą w agencji.
Regiony są ponumerowane od do w jakimkolwiek porządku.
Każdy pracownik z wyjątkiem Dyrektora posiada jednego bezpośredniego przełożonego.
Przełożony jest zawsze ważniejszy niż każdy z jego pracowników.
Powiemy, że pracownik jest menadżerem pracownika , wtedy i tylko wtedy,
gdy jest przełożonym lub jest menadżerem przełożonego .
W ten sposób, na przykład, Dyrektor jest menadżerem każdego z pozostałych
pracowników.
Ponadto, oczywiście, żadna para pracowników nie może być wzajemnie swoimi
menadżerami.
Niestety, Biuro Śledcze Narodów Zjednoczonych (UNBI) otrzymało ostatnio szereg
skarg na to, że struktura organizacyjna UNRDA nie jest zrównoważona
i wyróżnia pewne regiony świata w stosunku do innych.
Aby zweryfikować te oskarżenia, UNBI potrzebuje systemu komputerowego,
który dysponując strukturą organizacyjną UNRDA, mógłby odpowiadać na zapytania
postaci: dla dwóch różnych regionów i , ile jest par pracowników
agencji i , takich że pracownik pochodzi z regionu ,
pracownik pochodzi z regionu oraz jest menadżerem .
Każde zapytanie ma dwa parametry - regiony i - natomiast jego
wynikiem jest jedna liczba całkowita - liczba różnych par i ,
które spełniają wyżej wymienione warunki.
Zadanie
Napisz program, który mając dane regiony pochodzenia wszystkich pracowników
agencji, a także dane o tym, kto jest czyim przełożonym, odpowie na opisane wyżej zapytania.
Ograniczenia
- liczba pracowników
- liczba regionów
- liczba zapytań, na które ma odpowiedzieć twój program
- region pochodzenia pracownika (przy czym )
- przełożony pracownika (przy czym )
- regiony pojawiające się w danym zapytaniu
Wejście
Twój program powinien wczytać ze standardowego wejścia następujące dane:
- Pierwszy wiersz zawiera liczby całkowite , i , w tej
kolejności, pooddzielane pojedynczymi odstępami.
- Kolejne wierszy opisuje pracowników agencji w porządku
ważności.
-ty z tych wierszy opisuje pracownika numer .
Pierwszy z tych wierszy (tzn. ten opisujący Dyrektora) zawiera jedną
liczbę całkowitą: region pochodzenia Dyrektora.
Każdy z pozostałych wierszy zawiera dwie liczby całkowite oddzielone
pojedynczym odstępem: identyfikator przełożonego -tego pracownika
oraz region pochodzenia -tego pracownika.
- Następnie następuje opis zapytań. Każde zapytanie jest zawarte w jednym wierszu standardowego wejścia i składa
się z dwóch różnych liczb całkowitych oddzielonych pojedynczym odstępem -
regionów oraz .
Wyjście
Na standardowe wyjście wypisać należy wierszy, zawierających odpowiedzi na kolejne zapytania.
Odpowiedź na każde zapytanie musi być zawarta w jednym wierszu standardowego
wyjścia, zawierającym jedną liczbę całkowitą - liczbę par pracowników UNRDA
i , takich że regionem pochodzenia jest , regionem
pochodzenia jest oraz jest menadżerem .
Uwaga: Dane testowe będą tak dobrane, że poprawna odpowiedź na każde
z zapytań podanych na standardowym wejściu będzie zawsze mniejsza niż
.
Ocenianie
W testach wartych łącznie 30 punktów nie przekroczy 500.
W testach wartych łącznie 55 punktów z żadnego regionu nie będzie
pochodziło więcej niż 500 pracowników.
Testy, w których zachodzą oba powyższe warunki, są warte 15 punktów.
Testy, w których zachodzi co najmniej jeden z tych dwóch warunków, są warte 70 punktów.
Przykład
Dla danych wejściowych:
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
poprawną odpowiedzią jest:
1
3
2
1